//
// Created by DengLibin on 2019/1/5 0005.
//
#include <string>
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
/**
 * 回溯算法
 */

//给出n对括号，求括号排列的所有可能性
//分析:n对括号，左括号n个，右括号n个，取一个左括号就要取一个右括号

/**
 * 打印出所有可能的排列
 * @param leftNum  左括号数量
 * @param rightNum  右括号数量
 */
void parentheses(string s, int leftNum, int rightNum){
    //左右括号都用完了 打印排列结果
    if(leftNum == 0 && rightNum == 0){
        cout <<s<<endl;
    }
    //右括号比左括号多 取右括号
    if(rightNum > leftNum) {
        stringstream ss;
        ss<<s<<")";
        string s1 = ss.str();
        parentheses(s1, leftNum, rightNum - 1);
    }
    //左括号还有剩余 取左括号
    if(leftNum > 0){
        stringstream ss;
        ss<<s<<"(";
        string s1 = ss.str();
        parentheses(s1, leftNum - 1, rightNum);
    }
}

int main45(){
    string s = "";
    parentheses(s, 3,3);
    return 0;
}
